package MyTest;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T3 {
    public static int longest(String s, int l, int r) {
        int len = 0;
        while (l >= 0 && r < s.length()) {
            if (s.charAt(l) != s.charAt(r)) {
                return r - l - 1;
            }
            l--;
            r++;
        }

        return r - l - 1;
    }

    public static int longestValidParentheses(String s) {
        int len = s.length();
        if (len <= 1) {
            return 0;
        }
        if (len == 2) {
            return s.charAt(0) == '(' && s.charAt(1) == ')' ? 2 : 0;
        }

        int[] dp = new int[len];

        dp[0] = 0;
        dp[1] = (s.charAt(0) == '(' && s.charAt(1) == ')') ? 2 : 0;
        int maxx = Math.max(dp[1], 0);
        for (int j = 2; j < len; j++) {
            if (s.charAt(j) == '(') {
                dp[j] = 0;
            } else {
                if (s.charAt(j - 1) == '(') {
                    dp[j] = dp[j - 2]  + 2;
                } else if (j - dp[j - 1] - 1 >= 0 && s.charAt(j - dp[j - 1] - 1) == '(') {
                    if (j - dp[j - 1] - 2 >= 0) {
                        // s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”
                        dp[j] = dp[j - 1] + dp[j - dp[j - 1] - 2] + 2;
                    } else {
                        dp[j] = dp[j - 1] + 0 + 2;
                    }
                }
            }
            maxx = Math.max(maxx, dp[j]);
//            System.out.println(j+ " " + dp[j]);
        }
        return maxx;
    }

    public static void main(String[] args) {
        String ss = "()(()";
        System.out.println(longestValidParentheses(ss));
    }
}
